---
title: "填充"
created: 2025-11-28
tags:
  - 算法
---

# 填充

## 题目 [填充](https://www.acwing.com/problem/content/description/4969/)

![[image-27fe8802.png]]

## 思路分析

贪心问题也可以从集合去考虑

将一个问题划分成多个子集 若答案一定会出现在某个集合中 那么就用贪心 若要由多个集合综合而来 就需要用dp

若是贪心问题 直接将集合缩小成某个子集即可 类似于二分 抛开另一边不用管了

![[image-fc545112.png]]

在1110中 111能组成一种情况

这种情况一定会被11替换

所以只需要考虑相邻的两个数是否配对 若配对 跳过已配对里的第二个数 直接看它后面的数是否又与i+1配对

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1e6+10;

string s;

int main()

{

    cin>>s;

    int res=0;

    for(int i=0;i+1<s.size();i++){

        if(s[i]==s[i+1] || s[i]=='?' || s[i+1]=='?'){

            res++;

            i++; //1110中 前两个11已配对 就无需考虑后两个11是否配对 它们属于同一种情况 直接看第三个1和第四个0是否配对

        }

    }

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[（归并 逆序对性质）小朋友排队|（归并 逆序对性质）小朋友排队]] 🏠 [[00-刷题理模型]] ➡️ [[线性 短视 化大为小（类dp 集合分析）|线性 短视 化大为小（类dp 集合分析）]]